package com.leetcode;

import java.util.HashMap;

public class LRUCache {
    HashMap<Integer,Node> map;
    DoubleLinkedlist cache;
    int cap;
    public LRUCache(int capacity){
        map = new HashMap<>();
        cache = new DoubleLinkedlist();
        cap = capacity;
    }

    public int get(int key){
        if(!map.containsKey(key)) return -1;
        int val = map.get(key).val;
        put(key,val);
        return val;
    }

    public void put(int key,int value){
        Node newNode = new Node(key,value);
        if(map.containsKey(key)){
            cache.delete(map.get(key));
            map.put(key,newNode);
            cache.addFist(newNode);
        }else{
            if(map.size() == cap){
                cache.deleteLast();
                map.remove(key);
            }
            cache.addFist(newNode);
            map.put(key,newNode);
        }
    }
}

class DoubleLinkedlist{
    Node head;
    Node tail;
    public DoubleLinkedlist(){
        head = new Node(0,0);
        tail = new Node(0,0);
        head.next = tail;
        tail.prev = head;
    }

    public void addFist(Node node){
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public int delete(Node node){
        int key = node.key;
        node.prev.next = node.next;
        node.next.prev = node.prev;
        return key;
    }

    public int deleteLast(){
        if(head.next == tail) return -1;
        return delete(tail.prev);
    }

}

class Node{
    public int key;
    public int val;
    public Node prev;
    public Node next;
    public Node(int key,int val){
        this.val = val;
        this.key = key;
    }
}
